package fun.coding.leetcode;

public class DivideTwoIntegers {

	public static void main(String[] args) {
		System.out.println("Integer MIN is " + Integer.MIN_VALUE);
		// Wow, the abs of Integer.MIN is still itself, since the value is larger than Integer.MAX
		System.out.println("Integer MIN abs is " + Math.abs(Integer.MIN_VALUE));
		
		DivideTwoIntegers ins = new DivideTwoIntegers();
		System.out.println(ins.divide(5, 2));
		System.out.println(ins.divide(2147483647, 2));
		System.out.println(ins.divide(2147483647, 1));
		System.out.println(ins.divide(-1010369383, -2147483648));
		System.out.println(ins.divide(-2147483648, -1));
	}
	
	public int divide(int dividend, int divisor) {
		if (divisor == 0) return Integer.MAX_VALUE;
		
		boolean isPositive = true;
		if (dividend < 0) isPositive = !isPositive;
		if (divisor < 0) isPositive = !isPositive;
		
		// For the INT.MIN case
		long a = Math.abs((long)dividend);
		long b = Math.abs((long)divisor); // First cast it to long since abs(integer.min) is still negative
		
		// dividend / divisor = quotient...remainder
		long q = 0;
		
		while (b <= a) {
			int shift = 1;
			// If linear is too slow, then use shift for log/exponential growth
			while ((b << shift) < a) {
				shift++;
			}
			// need to be shift -1 since we are over shifting 1 bit in the while loop
			a = a - b * (1 << (shift - 1));
			q += 1 << (shift - 1);
		}
	
		if ((isPositive && q > Integer.MAX_VALUE) || (!isPositive && q < Integer.MIN_VALUE)) return Integer.MAX_VALUE;
		if (!isPositive) q =  -q; // negative just simply do -
		
		return (int)q;	
	}
	
	// This is O(N), just keep subtracting, but will exceed time limit
	public int divideLinear(int dividend, int divisor) {
		if (divisor == 0) return Integer.MAX_VALUE;
		
		boolean isPositive = true;
		if (dividend < 0) isPositive = !isPositive;
		if (divisor < 0) isPositive = !isPositive;
		
		dividend = Math.abs(dividend);
		divisor = Math.abs(divisor);
		
		// dividend / divisor = quotient...remainder
		int q = 0;
		
		while (dividend > divisor) {
			q++;
			dividend -= divisor;
		}
		
		if (!isPositive) q = -1 * q;
		
		return q;
	}
	

}
